<!DOCTYPE html>





<html class="theme-next muse use-motion" lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="generator" content="Hexo 3.9.0">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=7.3.0">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=7.3.0">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=7.3.0">
  <link rel="mask-icon" href="/images/logo.svg?v=7.3.0" color="#222">

<link rel="stylesheet" href="/css/main.css?v=7.3.0">


<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css?v=4.7.0">


<script id="hexo-configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Muse',
    version: '7.3.0',
    exturl: false,
    sidebar: {"position":"left","display":"post","offset":12,"onmobile":false},
    back2top: {"enable":true,"sidebar":false,"scrollpercent":false},
    save_scroll: false,
    copycode: {"enable":false,"show_result":false,"style":null},
    fancybox: false,
    mediumzoom: false,
    lazyload: false,
    pangu: false,
    algolia: {
      appID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    },
    localsearch: {"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},
    path: '',
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    translation: {
      copy_button: '复制',
      copy_success: '复制成功',
      copy_failure: '复制失败'
    }
  };
</script>

  <meta name="description" content="容器（Containers）顺序容器array [c++11]vector单开口，预留空间 emplace_back[c++11] 在最后构造并插入 list容器适配器stack后进先出 使用deque/list，不用vector的原因应该是容量大小有限制，扩容耗时 queue先进先出 使用deque/list，不用vector的原因应该是容量大小有限制，扩容耗时 deque关联容器setmapm">
<meta name="keywords" content="STL">
<meta property="og:type" content="article">
<meta property="og:title" content="STL从0开始">
<meta property="og:url" content="http://yoursite.com/2019/05/21/STL从0开始/index.html">
<meta property="og:site_name" content="XuQi&#39;s Blog">
<meta property="og:description" content="容器（Containers）顺序容器array [c++11]vector单开口，预留空间 emplace_back[c++11] 在最后构造并插入 list容器适配器stack后进先出 使用deque/list，不用vector的原因应该是容量大小有限制，扩容耗时 queue先进先出 使用deque/list，不用vector的原因应该是容量大小有限制，扩容耗时 deque关联容器setmapm">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2019-10-20T13:23:23.041Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="STL从0开始">
<meta name="twitter:description" content="容器（Containers）顺序容器array [c++11]vector单开口，预留空间 emplace_back[c++11] 在最后构造并插入 list容器适配器stack后进先出 使用deque/list，不用vector的原因应该是容量大小有限制，扩容耗时 queue先进先出 使用deque/list，不用vector的原因应该是容量大小有限制，扩容耗时 deque关联容器setmapm">
  <link rel="canonical" href="http://yoursite.com/2019/05/21/STL从0开始/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome: false,
    isPost: true,
    isPage: false,
    isArchive: false
  };
</script>

  <title>STL从0开始 | XuQi's Blog</title>
  








  <noscript>
  <style>
  .use-motion .motion-element,
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-title { opacity: initial; }

  .use-motion .logo,
  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  <div class="container sidebar-position-left">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta">

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">XuQi's Blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>


<nav class="site-nav">
  
  <ul id="menu" class="menu">
      
      
      
        
        <li class="menu-item menu-item-home">
      
    

    <a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i> <br>首页</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-archives">
      
    

    <a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i> <br>归档</a>

  </li>
  </ul>

    

</nav>
</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content page-post-detail">
            

  <div id="posts" class="posts-expand">
    

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://yoursite.com/2019/05/21/STL从0开始/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="XuQi">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/avatar.gif">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="XuQi's Blog">
    </span>
      <header class="post-header">

        
          <h1 class="post-title" itemprop="name headline">STL从0开始

            
          </h1>
        

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              
                
              

              <time title="创建时间：2019-05-21 20:22:36" itemprop="dateCreated datePublished" datetime="2019-05-21T20:22:36+00:00">2019-05-21</time>
            </span>
          
            

            
              <span class="post-meta-item">
                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                <span class="post-meta-item-text">更新于</span>
                <time title="修改时间：2019-10-20 13:23:23" itemprop="dateModified" datetime="2019-10-20T13:23:23+00:00">2019-10-20</time>
              </span>
            
          

          

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h2 id="容器（Containers）"><a href="#容器（Containers）" class="headerlink" title="容器（Containers）"></a>容器（Containers）</h2><h3 id="顺序容器"><a href="#顺序容器" class="headerlink" title="顺序容器"></a>顺序容器</h3><h4 id="array-c-11"><a href="#array-c-11" class="headerlink" title="array [c++11]"></a>array [c++11]</h4><h4 id="vector"><a href="#vector" class="headerlink" title="vector"></a>vector</h4><p>单开口，预留空间</p>
<p>emplace_back[c++11] 在最后构造并插入</p>
<h4 id="list"><a href="#list" class="headerlink" title="list"></a>list</h4><h3 id="容器适配器"><a href="#容器适配器" class="headerlink" title="容器适配器"></a>容器适配器</h3><h4 id="stack"><a href="#stack" class="headerlink" title="stack"></a>stack</h4><p>后进先出 使用deque/list，不用vector的原因应该是容量大小有限制，扩容耗时</p>
<h4 id="queue"><a href="#queue" class="headerlink" title="queue"></a>queue</h4><p>先进先出 使用deque/list，不用vector的原因应该是容量大小有限制，扩容耗时</p>
<h4 id="deque"><a href="#deque" class="headerlink" title="deque"></a>deque</h4><h3 id="关联容器"><a href="#关联容器" class="headerlink" title="关联容器"></a>关联容器</h3><h4 id="set"><a href="#set" class="headerlink" title="set"></a>set</h4><h4 id="map"><a href="#map" class="headerlink" title="map"></a>map</h4><h4 id="multiset"><a href="#multiset" class="headerlink" title="multiset"></a>multiset</h4><h4 id="multimap"><a href="#multimap" class="headerlink" title="multimap"></a>multimap</h4><h3 id="无序关联容器"><a href="#无序关联容器" class="headerlink" title="无序关联容器"></a>无序关联容器</h3><h4 id="unordered-set-c-11"><a href="#unordered-set-c-11" class="headerlink" title="unordered_set [c++11]"></a>unordered_set [c++11]</h4><h4 id="unordered-map-c-11"><a href="#unordered-map-c-11" class="headerlink" title="unordered_map [c++11]"></a>unordered_map [c++11]</h4><h4 id="unordered-multiset-c-11"><a href="#unordered-multiset-c-11" class="headerlink" title="unordered_multiset [c++11]"></a>unordered_multiset [c++11]</h4><h4 id="unordered-multimap-c-11"><a href="#unordered-multimap-c-11" class="headerlink" title="unordered_multimap [c++11]"></a>unordered_multimap [c++11]</h4><a id="more"></a>

<h4 id="容器分类"><a href="#容器分类" class="headerlink" title="容器分类"></a>容器分类</h4><h5 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h5><h6 id="数组-array-vector"><a href="#数组-array-vector" class="headerlink" title="数组  array/vector"></a><em>数组</em>  array/vector</h6><p>​    特点： 随机访问，vector删除数据时，空间不释放</p>
<h6 id="双向链表-list"><a href="#双向链表-list" class="headerlink" title="双向链表 list"></a><em>双向链表</em> list</h6><p>​    特点：快速增删</p>
<h6 id="双端队列-deque"><a href="#双端队列-deque" class="headerlink" title="双端队列 deque"></a><em>双端队列</em> deque</h6><p>​    特点: 随机访问，头尾快速增删</p>
<h6 id="红黑树-set-multiset-map-multimap"><a href="#红黑树-set-multiset-map-multimap" class="headerlink" title="红黑树    set/multiset  map/multimap"></a><em>红黑树</em>    set/multiset  map/multimap</h6><p>​    特点:插入删除性能相同O(log<sub>2</sub>n)</p>
<h6 id="哈希表-unordered-set-unordered-multiset-unordered-map-unordered-multimap"><a href="#哈希表-unordered-set-unordered-multiset-unordered-map-unordered-multimap" class="headerlink" title="哈希表 unordered_set/unordered_multiset unordered_map/unordered_multimap"></a><em>哈希表</em> unordered_set/unordered_multiset unordered_map/unordered_multimap</h6><p>​    特点: 最优O(1)，最差O(n)</p>
<h5 id="有序"><a href="#有序" class="headerlink" title="有序"></a>有序</h5><p>​    红黑树</p>
<h5 id="不可重复"><a href="#不可重复" class="headerlink" title="不可重复"></a>不可重复</h5><p>​    哈希+红黑树</p>
<blockquote>
<p>红黑树 R-B Tree，全称是Red-Black Tree 一种特殊的二叉查找树</p>
<p>红黑树的特性：</p>
<p>（1）每个节点或者是黑色，或者是红色。<br>（2）根节点是黑色。<br>（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]<br>（4）如果一个节点是红色的，则它的子节点必须是黑色的。<br>（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。</p>
</blockquote>
<blockquote>
<p>操作时间是：log n</p>
</blockquote>
<blockquote>
<p>AVL树-自平衡二叉查找树</p>
<p>特性：</p>
<p>（1）它的左子树和右子树都是AVL树 </p>
<p>（2）左子树和右子树的高度差不能超过1</p>
</blockquote>
<h4 id="顺序容器常用操作"><a href="#顺序容器常用操作" class="headerlink" title="顺序容器常用操作"></a>顺序容器常用操作</h4><table>
<thead>
<tr>
<th>iterators</th>
<th>const iterators</th>
<th>capacity</th>
<th>element access</th>
<th>modifiers</th>
<th>observers</th>
</tr>
</thead>
<tbody><tr>
<td>begin</td>
<td>cbegin</td>
<td>size</td>
<td>at</td>
<td>push_front</td>
<td>data</td>
</tr>
<tr>
<td>end</td>
<td>cend</td>
<td>empty</td>
<td>[]</td>
<td>pop_front</td>
<td></td>
</tr>
<tr>
<td>rbegin</td>
<td></td>
<td></td>
<td>front</td>
<td>push_back</td>
<td></td>
</tr>
<tr>
<td>rend</td>
<td></td>
<td></td>
<td>end</td>
<td>pop_back</td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
<td>erase</td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
<td>swap</td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
<td>clean</td>
<td></td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
<td></td>
<td>insert</td>
<td></td>
</tr>
</tbody></table>
<h4 id="关联容器-常用操作"><a href="#关联容器-常用操作" class="headerlink" title="关联容器 常用操作"></a>关联容器 常用操作</h4><table>
<thead>
<tr>
<th>operations</th>
<th>observers</th>
</tr>
</thead>
<tbody><tr>
<td>count</td>
<td>key_comp</td>
</tr>
<tr>
<td>find</td>
<td>value_comp</td>
</tr>
</tbody></table>
<h3 id="算法（Algorithms）"><a href="#算法（Algorithms）" class="headerlink" title="算法（Algorithms）"></a>算法（Algorithms）</h3><h5 id="头文件"><a href="#头文件" class="headerlink" title="头文件 "></a>头文件 <algorithm></algorithm></h5><h4 id="只读算法"><a href="#只读算法" class="headerlink" title="只读算法"></a>只读算法</h4><h5 id="查找算法"><a href="#查找算法" class="headerlink" title="查找算法"></a>查找算法</h5><table>
<thead>
<tr>
<th>函数</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>find(beg, end, v)</td>
<td>在[beg, end)之间查找等于v的元素，找到返回迭代器，找不到返回end</td>
</tr>
<tr>
<td>find_first_of(beg, end, beg2, end2)</td>
<td>在[beg, end)之间查找[beg2, end2)内任意匹配元素，找到返回的第一个容器中第一个匹配的元素</td>
</tr>
<tr>
<td>find_end(beg, end, beg2, end2)</td>
<td>找到最后匹配的元素</td>
</tr>
<tr>
<td>find_if(beg，end，func)</td>
<td>函数find的带一个函数参数的_if版本，与find功能相同，<strong>条件：使函数func返回true</strong></td>
</tr>
</tbody></table>
<h5 id="搜索与统计算法"><a href="#搜索与统计算法" class="headerlink" title="搜索与统计算法"></a>搜索与统计算法</h5><table>
<thead>
<tr>
<th>函数</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>search(beg, end, beg2, end2)</td>
<td>在区间1内搜索子序列2</td>
</tr>
<tr>
<td>search_n(beg, end,  n, v)</td>
<td>在区间[beg, end)内查找连续n个元素v</td>
</tr>
<tr>
<td>count(v)</td>
<td>统计v的个数</td>
</tr>
<tr>
<td>lower_bound(beg, end, v)</td>
<td>查找非递减序列，第一个大于v的元素</td>
</tr>
<tr>
<td>upper_bound(beg, end, v)</td>
<td>查找非递减序列，第一个小于v的元素</td>
</tr>
<tr>
<td>count_if(beg, end, v)</td>
<td>函数count的_if版本</td>
</tr>
</tbody></table>
<h4 id="可变序列算法"><a href="#可变序列算法" class="headerlink" title="可变序列算法"></a>可变序列算法</h4><table>
<thead>
<tr>
<th>函数</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>copy(beg, end, beg2)</td>
<td>将[beg, end)复制到beg2</td>
</tr>
<tr>
<td>transform(beg, end, beg2, func)</td>
<td>将每个元素经过func</td>
</tr>
<tr>
<td>replace(beg, end, v1, v2)</td>
<td>将[beg, end)中的v1替换v2</td>
</tr>
<tr>
<td>fill(beg, end,  v)</td>
<td>将[beg, end)写入v</td>
</tr>
<tr>
<td>fill_n(beg, n, v)</td>
<td>从beg写入n个v</td>
</tr>
<tr>
<td>generate(beg, n, rand)</td>
<td>从beg，填入n个随机数</td>
</tr>
<tr>
<td>remove(beg, end)</td>
<td>移除区间[beg, end)内元素，<strong>不是真正删除，只是移到最后</strong></td>
</tr>
<tr>
<td>unique(beg, end)</td>
<td>删除相邻重复元素，<strong>不是真正删除,只是移到最后</strong></td>
</tr>
<tr>
<td>remove_if(beg, end, func）</td>
<td>remove的_if版本</td>
</tr>
<tr>
<td>replace_if(beg，end，func，v2)</td>
<td>replace的_if版本</td>
</tr>
<tr>
<td>remove_copy(beg，end，dest)</td>
<td>remove的_copy版本，将反转后的序列输出到从dest开始的区间。</td>
</tr>
</tbody></table>
<h4 id="排序算法"><a href="#排序算法" class="headerlink" title="排序算法"></a>排序算法</h4><table>
<thead>
<tr>
<th>函数</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>sort(beg,end)</td>
<td>字典排序</td>
</tr>
<tr>
<td>stable_sort(beg,end)</td>
<td>字典排序。保存相等元素关系</td>
</tr>
<tr>
<td>parital_sort(beg,mid,end)</td>
<td>取mid - beg最小元素，放入[beg,mid)内</td>
</tr>
<tr>
<td>random_shuffle(beg,end)</td>
<td>随机排序</td>
</tr>
<tr>
<td>reverse(beg,end)</td>
<td>翻转</td>
</tr>
<tr>
<td>rotate(beg,mid,end)</td>
<td>[beg,mid)和[mid,end)元素旋转，并使用mid作为起点</td>
</tr>
<tr>
<td>merge(beg,end,beg2,end2,nbeg)</td>
<td>合并为一个，同时排序</td>
</tr>
<tr>
<td>reverse_cpoy(beg,end,dest)</td>
<td>reverse的copy</td>
</tr>
<tr>
<td>rotate_cpoy(beg,mid,end,dest)</td>
<td>rotate的copy</td>
</tr>
</tbody></table>
<h4 id="关系算法"><a href="#关系算法" class="headerlink" title="关系算法"></a>关系算法</h4><table>
<thead>
<tr>
<th>函数</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>equal(beg,end,beg1,end1)</td>
<td>判断两区间是否相同</td>
</tr>
<tr>
<td>include(beg1,end1,beg2,end2)</td>
<td>判断[beg2,end2)是否包含[beg1,end1)</td>
</tr>
<tr>
<td>max_element(beg,end)</td>
<td>返回最大元素</td>
</tr>
<tr>
<td>min_eleament(beg,end)</td>
<td>返回最小元素</td>
</tr>
<tr>
<td>mismatch(beg,end,beg1,end1)</td>
<td>查找两序列，第一个不匹配的的元素，返回一对it</td>
</tr>
</tbody></table>
<h4 id="堆算法"><a href="#堆算法" class="headerlink" title="堆算法"></a>堆算法</h4><blockquote>
<p>“堆”是个很有趣的数据结构，是个完全二叉树。</p>
<p>“堆”的特性：每个节点的键值一定总是大于（或小于）它的父节点（大于：称为“最大堆”，小于：称为“最小堆”），或者说每个节点总是大于或小于它的子节点。</p>
<p>对于最大堆而言，根节点为最大值；对于最小堆而言，根节点为最小值。</p>
<p>通常“堆”是通过数组来实现的，这样可以利用数组的特点快速定位指定索引的元素。</p>
</blockquote>
<blockquote>
<p><em>完全二叉树：</em>对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满。如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。这样的二叉树就是一棵完全二叉树。</p>
</blockquote>
<table>
<thead>
<tr>
<th>函数</th>
<th>描述</th>
</tr>
</thead>
<tbody><tr>
<td>make_heap(beg,end)</td>
<td>以区间[beg,end)建立堆</td>
</tr>
<tr>
<td>pop_heap(beg,end)</td>
<td>重新排序堆，第一个和最后一个交换，并不弹出正在最大值</td>
</tr>
<tr>
<td>push_heap(beg,end)</td>
<td>插入元素，重新排序堆</td>
</tr>
<tr>
<td>sort_heap(beg,end)</td>
<td>对序列重新排序</td>
</tr>
</tbody></table>
<h4 id="容器特有的算法"><a href="#容器特有的算法" class="headerlink" title="容器特有的算法"></a>容器特有的算法</h4><blockquote>
<p>因为list容器上的迭代器是双向的，所以不能使用随机访问的迭代器算法。</p>
</blockquote>
<p>参考链接：</p>
<p><a href="https://blog.csdn.net/xyqqwer/article/details/81263060" target="_blank" rel="noopener">https://blog.csdn.net/xyqqwer/article/details/81263060</a></p>
<h3 id="常见问题"><a href="#常见问题" class="headerlink" title="常见问题"></a>常见问题</h3><h5 id="STL有哪些组件？"><a href="#STL有哪些组件？" class="headerlink" title="STL有哪些组件？"></a>STL有哪些组件？</h5><blockquote>
<p>容器，迭代器，算法，容器适配器</p>
</blockquote>
<h5 id="STL常用的容器有哪些以及各自的特点是什么"><a href="#STL常用的容器有哪些以及各自的特点是什么" class="headerlink" title="STL常用的容器有哪些以及各自的特点是什么?"></a>STL常用的容器有哪些以及各自的特点是什么?</h5><h5 id="说说std-vector的底层（存储）机制。"><a href="#说说std-vector的底层（存储）机制。" class="headerlink" title="说说std::vector的底层（存储）机制。"></a>说说std::vector的底层（存储）机制。</h5><h5 id="什么情况下用vector，什么情况下用list。"><a href="#什么情况下用vector，什么情况下用list。" class="headerlink" title="什么情况下用vector，什么情况下用list。"></a>什么情况下用vector，什么情况下用list。</h5><h5 id="vector中begin和end函数返回的是什么？"><a href="#vector中begin和end函数返回的是什么？" class="headerlink" title="vector中begin和end函数返回的是什么？"></a>vector中begin和end函数返回的是什么？</h5><h5 id="为什么vector的插入操作可能会导致迭代器失效？"><a href="#为什么vector的插入操作可能会导致迭代器失效？" class="headerlink" title="为什么vector的插入操作可能会导致迭代器失效？"></a>为什么vector的插入操作可能会导致迭代器失效？</h5><blockquote>
<p>vector动态增加大小时，并不是在原空间后增加新的空间，而是以原大小的两倍在另外配置一片较大的新空间，然后将内容拷贝过来，并释放原来的空间。由于操作改变了空间，所以迭代器失效。</p>
</blockquote>
<h5 id="deque与vector的区别。"><a href="#deque与vector的区别。" class="headerlink" title="deque与vector的区别。"></a>deque与vector的区别。</h5><blockquote>
<p>1）vector是单向开口的连续线性空间，deque是双向开口的连续线性空间。（双向开口是指可以在头尾两端分别做元素的插入和删除操作）。</p>
<p>2）deque没有提供空间保留功能，而vector则要提供空间保留功能。</p>
<p>3）deque也提供随机访问迭代器，但是其迭代器比vector迭代器复杂很多。</p>
</blockquote>
<h5 id="不允许有遍历行为的容器有哪些（不提供迭代器）"><a href="#不允许有遍历行为的容器有哪些（不提供迭代器）" class="headerlink" title="不允许有遍历行为的容器有哪些（不提供迭代器）"></a>不允许有遍历行为的容器有哪些（不提供迭代器）</h5><blockquote>
<p>queue，stack，heap</p>
</blockquote>
<h5 id="说说std-map底层机制。"><a href="#说说std-map底层机制。" class="headerlink" title="说说std::map底层机制。"></a>说说std::map底层机制。</h5><h5 id="vector、list、map、deque用erase（it）后，迭代器的变化。"><a href="#vector、list、map、deque用erase（it）后，迭代器的变化。" class="headerlink" title="vector、list、map、deque用erase（it）后，迭代器的变化。"></a>vector、list、map、deque用erase（it）后，迭代器的变化。</h5><blockquote>
<p>vector和deque是序列式容器，其内存分别是连续空间和分段连续空间，删除迭代器it后，其后面的迭代器都失效了，此时it及其后面的迭代器会自动加1，使it指向被删除元素的下一个元素。</p>
<p>list删除迭代器it时，其后面的迭代器都不会失效，将前面和后面连接起来即可。</p>
<p>map也是只能使当前删除的迭代器失效，其后面的迭代器依然有效。</p>
</blockquote>
<h5 id="map和set的3个问题。"><a href="#map和set的3个问题。" class="headerlink" title="map和set的3个问题。"></a>map和set的3个问题。</h5><blockquote>
<p>1）为何map和set的插入删除效率比其他序列容器高。</p>
<p>因为不需要内存拷贝和内存移动</p>
<p>2）为何map和set每次Insert之后，以前保存的iterator不会失效？</p>
<p>因为插入操作只是结点指针换来换去，结点内存没有改变。而iterator就像指向结点的指针，内存没变，指向内存的指针也不会变。</p>
<p>3）当数据元素增多时（从10000到20000），map的set的查找速度会怎样变化？</p>
<p>RB-TREE用二分查找法，时间复杂度为log2n，所以从10000增到20000时，查找次数从log210000=14次到log220000=15次，多了1次而已。</p>
</blockquote>

    </div>

    
    
    
        
      

      <footer class="post-footer">
          
            
          
          <div class="post-tags">
            
              <a href="/tags/STL/" rel="tag"># STL</a>
            
          </div>
        

        

          <div class="post-nav">
            <div class="post-nav-next post-nav-item">
              
                <a href="/2018/05/17/Shadowsocks安装/" rel="next" title="shadowsocks">
                  <i class="fa fa-chevron-left"></i> shadowsocks
                </a>
              
            </div>

            <span class="post-nav-divider"></span>

            <div class="post-nav-prev post-nav-item">
              
                <a href="/2019/05/22/以太网芯片MAC和PHY的关系/" rel="prev" title="以太网芯片MAC和PHY的关系">
                  以太网芯片MAC和PHY的关系 <i class="fa fa-chevron-right"></i>
                </a>
              
            </div>
          </div>
        
      </footer>
    
  </div>
  
  
  
  </article>

  </div>


          </div>
          

        </div>
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-overview">

          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">XuQi</p>
  <div class="site-description motion-element" itemprop="description"></div>
</div>
  <nav class="site-state motion-element">
      <div class="site-state-item site-state-posts">
        
          <a href="/archives/">
        
          <span class="site-state-item-count">44</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
    
      
      
      <div class="site-state-item site-state-tags">
        
        
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
        <span class="site-state-item-count">30</span>
        <span class="site-state-item-name">标签</span>
        
      </div>
    
  </nav>



        </div>
      </div>
      <!--noindex-->
        <div class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
            
            
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-2"><a class="nav-link" href="#容器（Containers）"><span class="nav-number">1.</span> <span class="nav-text">容器（Containers）</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#顺序容器"><span class="nav-number">1.1.</span> <span class="nav-text">顺序容器</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#array-c-11"><span class="nav-number">1.1.1.</span> <span class="nav-text">array [c++11]</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#vector"><span class="nav-number">1.1.2.</span> <span class="nav-text">vector</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#list"><span class="nav-number">1.1.3.</span> <span class="nav-text">list</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#容器适配器"><span class="nav-number">1.2.</span> <span class="nav-text">容器适配器</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#stack"><span class="nav-number">1.2.1.</span> <span class="nav-text">stack</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#queue"><span class="nav-number">1.2.2.</span> <span class="nav-text">queue</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#deque"><span class="nav-number">1.2.3.</span> <span class="nav-text">deque</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#关联容器"><span class="nav-number">1.3.</span> <span class="nav-text">关联容器</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#set"><span class="nav-number">1.3.1.</span> <span class="nav-text">set</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#map"><span class="nav-number">1.3.2.</span> <span class="nav-text">map</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#multiset"><span class="nav-number">1.3.3.</span> <span class="nav-text">multiset</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#multimap"><span class="nav-number">1.3.4.</span> <span class="nav-text">multimap</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#无序关联容器"><span class="nav-number">1.4.</span> <span class="nav-text">无序关联容器</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#unordered-set-c-11"><span class="nav-number">1.4.1.</span> <span class="nav-text">unordered_set [c++11]</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#unordered-map-c-11"><span class="nav-number">1.4.2.</span> <span class="nav-text">unordered_map [c++11]</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#unordered-multiset-c-11"><span class="nav-number">1.4.3.</span> <span class="nav-text">unordered_multiset [c++11]</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#unordered-multimap-c-11"><span class="nav-number">1.4.4.</span> <span class="nav-text">unordered_multimap [c++11]</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#容器分类"><span class="nav-number">1.4.5.</span> <span class="nav-text">容器分类</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#数据结构"><span class="nav-number">1.4.5.1.</span> <span class="nav-text">数据结构</span></a><ol class="nav-child"><li class="nav-item nav-level-6"><a class="nav-link" href="#数组-array-vector"><span class="nav-number">1.4.5.1.1.</span> <span class="nav-text">数组  array/vector</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#双向链表-list"><span class="nav-number">1.4.5.1.2.</span> <span class="nav-text">双向链表 list</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#双端队列-deque"><span class="nav-number">1.4.5.1.3.</span> <span class="nav-text">双端队列 deque</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#红黑树-set-multiset-map-multimap"><span class="nav-number">1.4.5.1.4.</span> <span class="nav-text">红黑树    set/multiset  map/multimap</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#哈希表-unordered-set-unordered-multiset-unordered-map-unordered-multimap"><span class="nav-number">1.4.5.1.5.</span> <span class="nav-text">哈希表 unordered_set/unordered_multiset unordered_map/unordered_multimap</span></a></li></ol></li><li class="nav-item nav-level-5"><a class="nav-link" href="#有序"><span class="nav-number">1.4.5.2.</span> <span class="nav-text">有序</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#不可重复"><span class="nav-number">1.4.5.3.</span> <span class="nav-text">不可重复</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#顺序容器常用操作"><span class="nav-number">1.4.6.</span> <span class="nav-text">顺序容器常用操作</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#关联容器-常用操作"><span class="nav-number">1.4.7.</span> <span class="nav-text">关联容器 常用操作</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#算法（Algorithms）"><span class="nav-number">1.5.</span> <span class="nav-text">算法（Algorithms）</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#头文件"><span class="nav-number">1.5.0.1.</span> <span class="nav-text">头文件 </span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#只读算法"><span class="nav-number">1.5.1.</span> <span class="nav-text">只读算法</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#查找算法"><span class="nav-number">1.5.1.1.</span> <span class="nav-text">查找算法</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#搜索与统计算法"><span class="nav-number">1.5.1.2.</span> <span class="nav-text">搜索与统计算法</span></a></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#可变序列算法"><span class="nav-number">1.5.2.</span> <span class="nav-text">可变序列算法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#排序算法"><span class="nav-number">1.5.3.</span> <span class="nav-text">排序算法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#关系算法"><span class="nav-number">1.5.4.</span> <span class="nav-text">关系算法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#堆算法"><span class="nav-number">1.5.5.</span> <span class="nav-text">堆算法</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#容器特有的算法"><span class="nav-number">1.5.6.</span> <span class="nav-text">容器特有的算法</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#常见问题"><span class="nav-number">1.6.</span> <span class="nav-text">常见问题</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#STL有哪些组件？"><span class="nav-number">1.6.0.1.</span> <span class="nav-text">STL有哪些组件？</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#STL常用的容器有哪些以及各自的特点是什么"><span class="nav-number">1.6.0.2.</span> <span class="nav-text">STL常用的容器有哪些以及各自的特点是什么?</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#说说std-vector的底层（存储）机制。"><span class="nav-number">1.6.0.3.</span> <span class="nav-text">说说std::vector的底层（存储）机制。</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#什么情况下用vector，什么情况下用list。"><span class="nav-number">1.6.0.4.</span> <span class="nav-text">什么情况下用vector，什么情况下用list。</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#vector中begin和end函数返回的是什么？"><span class="nav-number">1.6.0.5.</span> <span class="nav-text">vector中begin和end函数返回的是什么？</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#为什么vector的插入操作可能会导致迭代器失效？"><span class="nav-number">1.6.0.6.</span> <span class="nav-text">为什么vector的插入操作可能会导致迭代器失效？</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#deque与vector的区别。"><span class="nav-number">1.6.0.7.</span> <span class="nav-text">deque与vector的区别。</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#不允许有遍历行为的容器有哪些（不提供迭代器）"><span class="nav-number">1.6.0.8.</span> <span class="nav-text">不允许有遍历行为的容器有哪些（不提供迭代器）</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#说说std-map底层机制。"><span class="nav-number">1.6.0.9.</span> <span class="nav-text">说说std::map底层机制。</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#vector、list、map、deque用erase（it）后，迭代器的变化。"><span class="nav-number">1.6.0.10.</span> <span class="nav-text">vector、list、map、deque用erase（it）后，迭代器的变化。</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#map和set的3个问题。"><span class="nav-number">1.6.0.11.</span> <span class="nav-text">map和set的3个问题。</span></a></li></ol></li></ol></li></ol></li></ol></div>
            

          </div>
        </div>
      <!--/noindex-->
      

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2019</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">XuQi</span>
</div>
  <div class="powered-by">由 <a href="https://hexo.io" class="theme-link" rel="noopener" target="_blank">Hexo</a> 强力驱动 v3.9.0</div>
  <span class="post-meta-divider">|</span>
  <div class="theme-info">主题 – <a href="https://theme-next.org" class="theme-link" rel="noopener" target="_blank">NexT.Muse</a> v7.3.0</div>

        








        
      </div>
    </footer>
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
      </div>

    

  </div>

  
  <script src="/lib/jquery/index.js?v=3.4.1"></script>
  <script src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  <script src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>

<script src="/js/utils.js?v=7.3.0"></script>
  <script src="/js/motion.js?v=7.3.0"></script>


  <script src="/js/schemes/muse.js?v=7.3.0"></script>


<script src="/js/next-boot.js?v=7.3.0"></script>




  




























  

  

  


  
  <script src="/js/scrollspy.js?v=7.3.0"></script>
<script src="/js/post-details.js?v=7.3.0"></script>


</body>
</html>
